package LC;

/**
 * @ClassName LC450
 * @Description: TODO
 * @Author hl
 * @Date 2020/5/26
 * @Version V1.0
 **/
 class TreeNode {
    int val;
     TreeNode left;
    TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class LC450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return  null;
        }
        if(root.val<key){
            root.right=deleteNode(root.right,key);
        }else{
            if(root.val>key){
                root.left=deleteNode(root.left,key);
            }else{
                if(root.left==null&&root.right==null){
                   root=null;
                }else{
                    if(root.right!=null){
                        root.val=seachAfter(root);
                        root.right=deleteNode(root.right,root.val);
                    }else {
                        root.val=seachPre(root);
                        root.left=deleteNode(root.left,root.val);
                    }
                }

            }
        }
        return root;
    }
    public int seachAfter(TreeNode root){
        //因为在deleteNode函数已经限定了进入seachAfter的函数不会为null，而且root.right也不会为null
        // 所以这里不需要判定root为null
        root=root.right;
        while(root.left!=null){
            root=root.left;
        }
        return  root.val;
    }
    public int seachPre(TreeNode root){
        //因为在deleteNode函数已经限定了进入seachPre的函数不会为null，而且root.right也不会为null
        root=root.left;
        while(root.right!=null){
            root=root.right;
        }
        return root.val;
    }
}
